package com.c2b.algorithm.newcoder.double_pointer;

import java.util.ArrayList;
import java.util.Comparator;

/**
 * <a href="">合并区间</a>
 * <p>
 * 给出一组区间，请合并所有重叠的区间。请保证合并后的区间按区间起点升序排列。<br>
 * 数据范围：区间组数0≤n≤2×10^5，区间内 的值都满足0≤val≤2×10^5<br>
 * 要求：空间复杂度O(n)，时间复杂度O(nlogn)<br>
 * 进阶：空间复杂度O(val)，时间复杂度O(val)<br>
 * </p>
 *
 * @author c2b
 * @since 2023/3/15 18:43
 */
public class BM0089Merge_M {

    public static class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }

    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        intervals.sort(Comparator.comparingInt(i -> i.start));
        ArrayList<Interval> resultList = new ArrayList<>();
        // 从虚拟位置开始
        int index = -1;
        for (Interval interval : intervals) {
            // 不合并
            if (index == -1 || intervals.get(index).end < interval.start) {
                resultList.add(interval);
                index++;
            } else {
                // 如果有重叠区间，那么就需要找到重叠的两个interval的最大end作为右边的边界
                resultList.get(index).end = Math.max(interval.end, resultList.get(index).end);
            }
        }
        return resultList;
    }

    public static void main(String[] args) {
        ArrayList<Interval> arrayList = new ArrayList<>();
        arrayList.add(new Interval(10, 30));
        arrayList.add(new Interval(20, 60));
        arrayList.add(new Interval(80, 100));
        arrayList.add(new Interval(150, 180));

        BM0089Merge_M bm0089Merge_m = new BM0089Merge_M();
        ArrayList<Interval> arrayList1 = bm0089Merge_m.merge(arrayList);
    }
}
